/**
 * 最大子序列：
 *  寻找数组中存在的最大连续子序列，此序列只有数组元素存在负数时才有意义.
 * 分治策略：
 * nleft, nmid, nright
 * 子序列:
 *      nleft <= i && j <= nmid 
 *      nmid <= i && j <= nright
 *      nleft <= i(mid) && j(mid) <= nright
 * 无论是子序列存与左边还是右边，都可以转换成横跨中间的问题.
 */
#include <functional>
#include <stdio.h>
#include <tuple>

#if __cplusplus >= 201103L
#include <limits>

#define MIN_LIMIT(T) std::numeric_limits<T>::min()
#define MAX_LIMIT(T) std::numeric_limits<T>::max()
#else
    #define MIN_LIMIT(T) 0x80000000
    #define MAX_LIMIT(T) 0x7fffffff
#endif // __cplusplus

template<typename T = int>
void tPrintf(const std::tuple<int, int, T>& value){
    printf("%d, %d, %d\n", std::get<0>(value), std::get<1>(value), std::get<2>(value));
}
/**
 * 查询横跨中间的最长子序列.
 */
template<typename T, typename compare = std::less<T>>
std::tuple<int, int, T> FindMidMaxSubArray(T* pElems, int nLeft, int nMid, int nRight){
    compare comp;

    T sum = 0;
    T left_sum = MIN_LIMIT(T);
    int left_index = -1;
    int i = nMid;
    while(i >= nLeft){
        printf("[[%d, %d]]\n", i, nLeft);
         sum += pElems[i];
         if(comp(left_sum, sum)){
             left_sum = sum;
             left_index = i;
         }
         --i;
    }

    T right_sum = MIN_LIMIT(T);
    int right_index = -1;
    sum = 0;
    i = nMid + 1;
    while(i <= nRight){
        sum += pElems[i];
        if(comp(right_sum, sum)){
            right_sum = sum;
            right_index = i;
        }
        ++i;
    }

    return std::make_tuple(left_index, right_index, left_sum + right_sum);
}

template<typename T, typename greater_equal = std::greater_equal<T>, typename less = std::less<T>>
std::tuple<int, int, T> FindMaximumSubArray(T* pElems, int nLeft, int nRight){
    if(nLeft == nRight){ //指向同一个元素时.
        return std::make_tuple(nLeft, nRight, pElems[nLeft]);
    }else{
        printf("[[------------------\n");
        int nMid = (nLeft + nRight) / 2;
        printf("%d\n", nMid);
        auto leftResult = FindMaximumSubArray<T, less>(pElems, nLeft, nMid);
        tPrintf(leftResult);
        auto rightResult = FindMaximumSubArray<T, less>(pElems, nMid + 1, nRight);
        tPrintf(rightResult);
        auto midResult = FindMidMaxSubArray<T, less>(pElems, nLeft, nMid, nRight);
        tPrintf(midResult);
         printf("------------------]]\n");
        greater_equal g_equal;
        if(g_equal(std::get<2>(leftResult), std::get<2>(rightResult)) &&
                std::get<2>(leftResult) >= std::get<2>(midResult))
            return leftResult;
        else if(g_equal(std::get<2>(rightResult), std::get<2>(leftResult)) &&
                std::get<2>(rightResult) >= std::get<2>(midResult))
            return rightResult;
        else
            return midResult;
    }
}

int main(int argc, char const *argv[]) {
    printf("%d, %d", MIN_LIMIT(int), MAX_LIMIT(int));

    int nElements[] = {13,-1,-25,20,-3, -16,-23,18,20,-7,12,-5,-22,15,-4, 7};
    auto maxSub = FindMaximumSubArray(nElements, 0, sizeof(nElements) / sizeof(int) - 1);

    tPrintf(maxSub);
    return 0;
}

